package work.dp;

public class Problem42 {
    public int trap(int[] height) {
        int[] left = new int[height.length];
        int[] right = new int[height.length];
        int ans = 0;
        left[0] = height[0];
        for (int i = 1; i < height.length; i++) {
            left[i] = Math.max(height[i], left[i - 1]);
        }
        right[height.length - 1] = height[height.length - 1];
        for (int j = height.length - 2; j >= 0; j--) {
            right[j] = Math.max(height[j], right[j + 1]);
        }
        for (int k = 0; k < height.length; k++) {
            ans += Math.min(left[k], right[k]) - height[k];
        }
        return ans;
    }

    public static void main(String[] args) {
        Problem42 problem42 = new Problem42();
        int[] height1 = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        problem42.trap(height1);
    }
}
